// @FileName  :find.c
// @Time      :2024/5/20 16:57
// @Author    :YKW
//# include <bits/stdc++.h>
//using namespace std;
# include <stdio.h>
# include <stdlib.h>
# include <math.h>
# include <string.h>
# include <stdlib.h>

#define NHASH  3001
#define MULT  37

char dic[3500][30], word[30];
int cho, cnt, find, ccnt;
int ind[30];
struct node {
    char w[30];
    struct node *nxt;
} *hsTable[3500];

unsigned int hash(char *str) {
    unsigned int h = 0;
    char *p;
    for (p = str; *p != '\0'; p++)
        h = MULT * h + *p;
    return h % NHASH;
}

void buildHash() {
    for (int i = 0; i < cnt; i++) {
        hsTable[i] = NULL;
    }
    for (int i = 0; i < cnt; i++) {
        int hs = hash(dic[i]);
        if (hsTable[hs] == NULL) {
            hsTable[hs] = (struct node *) malloc(sizeof(struct node));
            strcpy(hsTable[hs]->w, dic[i]);
            hsTable[hs]->nxt = NULL;
        } else {
            struct node *p = hsTable[hs];
            while (strcmp(p->w, dic[i]) < 0) {
                if (p->nxt == NULL ||
                    strcmp(p->nxt->w, dic[i]) > 0)
                    break;
                else
                    p = p->nxt;
            }
            struct node *neo = (struct node *) malloc(sizeof(struct node));
            strcpy(neo->w, dic[i]);
            neo->nxt = p->nxt;
            p->nxt = neo;
        }
    }
}

int main() {
    setbuf(stdout, NULL);
    FILE *fin = fopen("dictionary3000.txt", "r");
    while (fscanf(fin, "%s", dic[cnt++]) != EOF) {
        ind[dic[cnt - 1][0] - 'a' + 1] = cnt - 1;
    }
    ind[0] = -1;
    ind[24] = ind[23];//没有x开头单词
//    freopen("dictionary3000.txt", "r", stdin);
//    while (scanf("%s", dic[cnt++]) != EOF) {
//        ind[dic[cnt - 1][0] - 'a' + 1] = cnt;
//    }
//    fclose(stdin);
    buildHash();
    while (scanf("%s%d", word, &cho) != EOF) {
        ccnt = find = 0;
        if (cho == 1) {//顺序
            for (ccnt = 0; ccnt < cnt;) {
                int res = strcmp(word, dic[ccnt]);
                ccnt++;
                if (res == 0) {
                    find = 1;
                    break;
                } else if (res < 0)
                    break;
            }
        } else if (cho == 2) {//折半
            int l = 0, r = cnt - 2, mid;
            while (l <= r) {
                mid = (l + r) / 2;
                int res = strcmp(word, dic[mid]);
                ccnt++;
                if (res == 0) {
                    find = 1;
                    break;
                } else if (res < 0)
                    r = mid - 1;
                else
                    l = mid + 1;
            }
        } else if (cho == 3) {//索引表
            int l = ind[word[0] - 'a'] + 1, r = ind[word[0] - 'a' + 1], mid;
            while (l <= r) {
                mid = (l + r) / 2;
                int res = strcmp(word, dic[mid]);
                ccnt++;
                if (res == 0) {
                    find = 1;
                    break;
                } else if (res < 0)
                    r = mid - 1;
                else
                    l = mid + 1;
            }
        } else {//HASH
            int hs = hash(word);
            struct node *p = hsTable[hs];
            while (p != NULL) {
                int res = strcmp(word, p->w);
                ccnt++;
                if (res == 0) {
                    find = 1;
                    break;
                } else if (res > 0)
                    p = p->nxt;
                else
                    break;
            }
        }
        printf("%d %d\n", find, ccnt);
    }
}